// 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
// 你从其中的一个加油站出发，开始时油箱为空。
// 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
// 思路，贪心1
// 一旦[0，i] 区间和为负数，起始位置就可以是i+1

function canCompleteCircuit(gas, cost) {
    let start = 0
    let curSum = 0
    let totalSum = 0
    for (let i = 0; i < gas.length; i++) {
        curSum += gas[i] - cost[i]
        totalSum += gas[i] - cost[i]
        if (curSum < 0) {
            start = i + 1
            curSum = 0
        }        
    }
    if (totalSum < 0) {
        return -1
    }
    return start
}

let gas = [1,2,3,4,5], cost = [3,4,5,1,2]
console.log(canCompleteCircuit(gas, cost))


// 思路，贪心2
// 如果剩余油量总和小于0，则不可能跑完一圈
// 如果剩余最小油量大于0，则返回0
// 否则从后往前，把这个最小剩余油量填满的时候，说明该位置可以跑完一圈
function canCompleteCircuit2(gas, cost) {
    let totalSum = 0
    let minSum = Infinity // 最小的和默认是Infinity
    for (let i = 0; i < gas.length; i++) {
        totalSum += gas[i] - cost[i]
        minSum = Math.min(minSum, totalSum)      
    }
    if (totalSum < 0) {
        return -1
    }
    if (minSum >=0) {
        return 0
    }
    for (let i = gas.length -1; i >=0; i--) {
        minSum += gas[i] - cost[i]
        if (minSum >= 0) {
            return i
        }        
    }
    return -1
}

console.log(canCompleteCircuit2(gas, cost))